package com.example.algorithm.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/7/25
 * 四数之和
 */
public class FourCount {


    /**
     * 四数之和，其实就是在三数之和的基础上继续再套一层
     * @param num
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int []num,int target) {
        int len=num.length;
        List<List<Integer>> list=new ArrayList<>();
        Arrays.sort(num);
        for(int i=0;i<len;i++)
        {
            if(i>0&&num[i-1]==num[i]){
                continue;
            }
            if(num[i]>0&&num[i]>target){
                return list;
            }
            for(int j=i+1;j<len;j++)
            {
                int left=j+1;
                int right=len-1;
                if(j>i+1&&num[j]==num[j-1])
                {
                    continue;
                }
                while(left<right)
                {
                    long sum=num[i]+num[j]+num[left]+num[right];
                    if(sum<target){
                        left++;
                    }else if(sum>target){
                        right--;
                    }else {
                        list.add(Arrays.asList(num[i],num[j],num[left],num[right]));
                        while(right>left&&num[right]==num[right--]){
                            right--;
                        }
                        while (right>left&&num[left]==num[left++]){
                            left++;
                        }
                        right--;
                        left++;
                    }
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {

    }
}
